package com.love.labuladong;


import java.util.Arrays;

/**
 * @Author : zh
 * @Description : 快速排序
 * @Date : 2024-07-18 10:57
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] arr = {3,5,2,1,4,2,4,5,7,8,6,5};
//        sort(arr);

        System.out.println(Arrays.toString(arr));

        int p = partition3(arr, 0, arr.length - 1, 5);


        System.out.println(Arrays.toString(arr));
        System.out.println(p);
    }


    private static void sort(int[] arr){
       quickSort1(arr,0,arr.length - 1);
//        quickSort2(arr,0,arr.length - 1);
    }

    // 经典排序算法
    public static void quickSort1(int[] arr,int l,int r){
        // l > r : 表示空集
        // l = r : 表示只有一个
        if(l >= r){
            return;
        }
        // 在数组中随机选一个数
        int x = arr[ l + (int) (Math.random() * (r - l + 1))];
//        int p = partition1(arr,l,r,x);
        int p = partition3(arr,l,r,x);
        quickSort1(arr,l,p-1);
        quickSort1(arr,p+1,r);

    }

    // 已知 arr[l ... r] 范围上一定有 x 这个值
    // 划分数组 <= x 放左边， >x 放右边，并且确保划分完成之后 <= x 区域的最后一个数字是 x
    private static int partition1(int[] arr, int l, int r, int x) {
        int slow = l,fast = l;
        // 快慢指针通向而行
        // slow 遇到 >x ，即 arr[slow] > x, slow 就卡住， fast 继续前行，遇到 < x 的数，就和 slow 交换
        // 最后形成的排序就是，slow左边的全是 <= x 的数，当然 slow ... r 都是 >x 的数
        // 但是 x 不一定排在，slow左边的最后一个（x该待的位置），随意要把他换到这个位置

        int index = 0;

        while (fast <= r){
            if(arr[fast] <= x){
                swap(arr,slow,fast);
                if(arr[slow] == x){
                    index = slow;
                }
                slow++;
            }
            fast++;
        }
        swap(arr,index,slow - 1);
        return slow - 1;
    }


    private static void swap(int[] arr,int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    public static int first, last;

    public static void quickSort2(int[] arr,int l,int r){
        // l > r : 表示空集
        // l = r : 表示只有一个
        if(l >= r){
            return;
        }
        // 在数组中随机选一个数
        int x = arr[ l + (int) (Math.random() * (r - l + 1))];
        partition2(arr,l,r,x);
        int left = first;
        int right = last;
        quickSort2(arr,l,left - 1);
        quickSort2(arr,right + 1,r);

    }


    // 方法二（推荐）
    // 已知 arr[l ... r] 范围上一定有 x 这个值
    // 划分数组 <= 放左边， ==x 放中间， >x 放右边
    // 把全局变量first,last,更新成 ==x 区间的左右边界
    private static void partition2(int[] arr, int l, int r, int x) {
        // 三指针
        int i = l;
        while (i <= r){
            if(arr[i] == x){
                i++;
            }else if(arr[i] < x){
                swap(arr,l++,i++);
            }else {
                swap(arr,i,r--);
            }
        }
        first = l;
        last = r;
    }


    // 方法三
    // 和 partition1 的效果一样
    // 已知 arr[l ... r] 范围上一定有 x 这个值
    // 划分数组 <= x 放左边， >x 放右边，并且确保划分完成之后 <= x 区域的最后一个数字是 x
    private static int partition3(int[] arr,int l,int r,int x){

        int index = 0;
        // 这个地方是 对向滑动窗口 左右指针相向而行，左指针走过的地方都是 <= x的，右指针走过的地方都是 > x 的值
        int left = l,right = r;

        while (left <= right){
            while (left <= right && arr[left] <= x){
                if(arr[left] == x){
                    index = left;
                }
                left++;
            }

            while (right >= left && arr[right] > x ){
                right--;
            }
            // 左右指针相碰了，代表 左  x  右 排好了
            if(left >= right){
                break;
            }
            // 左右指针还没相碰，左指针碰到了>x的值且右指针遇到<=x的值，所以左右指针都卡住了。
            // 交换左右值指针的值，让他们继续循环判断，直到两个指针相碰
            swap(arr,left,right);
        }
        // 以上的操作完成了 [左]<=x,右>x,那么x是不是应该放在[左]的最右的一位
        // 但是以上的操作不一定把 x 放到 [左]的最右的一位，
        // 所以在遍历的过程中要记录 x 的位置，然后把他放到 [左]的最右的一位
        swap(arr,index,right);

        return right;
    }

}
